数据结构之——链表

课程《玩转数据结构》学习

  • 链表与数组
  • 使用虚拟头节点
  • 链表的增删改查
  • 链表的时间复杂度分析
  • 使用链表实现栈与队列

链表与数组

链表是典型的线性动态数据结构，也是学习树形数据结构的敲门砖。与数组不同，链表的意义在于动态二字。再回顾一下什么是数组：在内存中开辟一段连续的存储空间的相同数据类型元素存储的集合 。数组并不具备动态的能力，为了让数组具有动态的特性，我们可以实现自己的数组，让其具备自动扩容以及缩容(resize)的能力。动态数组。
而对于栈,与队列这两种具备特殊功能的线性数据结构，可以使用数组作为底层原理来实现。对于栈的特性即LIFO,使用动态数组作为底层实现满足了栈各个功能的时间复杂度为O(1)。而队列的特性为：FIFO，如果使用数组作为底层，在队列的出队操作时，这一项功能的时间复杂度就为O(n)。使用循环队列的思想，则可以将出队操作优化至O(1)。
链表则是一种真正的动态数据结构。因为数组在内存的空间是连续的，所以最大的优势 是支持“随机访问”，而链表最大的优点则是“真正的动态”。链表不会浪费多余的内存空间，不需要处理容量的问题，但是也丧失了数组的随机访问的能力。

image-20190803092419079

上图表示的就是一个链表，图中的圆形表示为链表中的一个节点，每个节点都存储着下一个节点的引用。链表的尾部，也就是链中最后一个节点，是没有指向下一个节点的，所以自然指向了Null。要想实现 “一个节点存储着下一个节点的引用”功能并不难，我们只需要在链表类中，增加一个内部类Node即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class LinkedList<E>{
    private class Node{
        public E e;// 存储数据
        public Node next;// 指向下一个节点
        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }
    // 指向链表头
    private Node head;
    private int size;
    public LinkedList(){
        head = null;
        size = 0;
    }
    //  获取链表中元素的个数
    public int getSize(){
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty(){
        return size==0;
    }
}

链表中每一个节点都存储着下一个节点的引用，那么谁来存储链表头部的引用呢？所以，与数组不同，链表需要额外去维护一个变量，这个变量我们称作head,用于存储链表头的引用。

使用虚拟头节点

现在向链表添加元素。
我们需要考虑两种情况，第一种情况为：向链表头部添加元素。

image-20190803092437986

在向链表头部添加元素时，我们需要：

1
2
3
1：newNode.next = head;// 将添加的节点的next指向head
2: head = newNode;// 将head再次指向头部
复制代码

实现代码为：

1
2
3
4
5
public void addFirst(E e){
    head = new Node(e,head);
    size++;
}
复制代码

还有一种情况是：在链表任意位置添加元素，这一点和在链表头部添加元素略有不同。(普遍来讲，当你选择了链表这种数据结构时，往往不会涉及向链表的中间添加元素，实现此功能是为了更加深入地学习链表)

image-20190803092456660

我们考虑一下，在链表中间插入元素时，假设插入位置的”索引”称作index。我们首先需要将插入的节点指向index处的节点，本图为向index==2的位置插入元素99。然后再将index位置前的一个节点指向被插入的节点，那么我们如何获取index-1处的节点呢？答案就是遍历。我们需要一个特殊的变量，让它指向index-1处的节点，现在用prev表示这个变量，最初让,每次让,遍历index-1次，就可以获得index-1处的，也就是待插入位置的前一个位置的索引处的节点。插入的过程为：

1
2
3
1: newNode.next = prev.next
2: prev.next = newNode
复制代码

代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void add(int index,E e){
    if(index<0 || index>size)
        throw new IllegalArgumentException("Index is Illegal");
    if(index==0){
        // 如果在链表头部添加元素
        addFirst(e);
    }else{
        Node prev = head;
        for(int i=0;i<index-1;i++){
            prev = prev.next;
        }
        prev.next = new Node(e,prev.next);
        size++;
    }
}
复制代码

如果使用head这个变量去维护链表头自然是可以的，但是我们看到了，我们的链表在头部添加元素时，和在其他位置添加元素的思路是不一样的。有没有办法能够将链表进行优化，使得链表的头部同链表的其他位置在增删改查的操作一致呢？使用虚拟头节点就可以优化链表，解决这样的一个问题。

image-20190803092512121

如上图所示，我们在原本的head前使用一个dummyHead这样的一个变量，让它指向原本的head，这样对于我们来讲，链表中所有的节点都满足了“有指向它的节点”这样一个特性。

链表的增删改查

有了dummyHead虚拟头节点后，链表的增删改查都会变的非常容易。

向链表中添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(int index,E e){
    if(index<0 || index>e)
        throw new IllegalArgumentException("Index is Illegal");
    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    prev.next = new Node(e,prev.next);
    size++;
}
// 在链表头添加新的元素e
public void addFirst(E e){
    add(0,e);
}
// 在链表尾添加新的元素e
public void addLast(E e){
    add(size,e);
}

向链表中删除元素

image-20190803092528071

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E remove(int index){
    if(index<0 || index>=size)
        throw new IllegalArgumentException("index is Illegal");
    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    E delNode = prev.next;
    prev.next = prev.next.next; // prev.next = delNode.next;
    delNode.next = null;
    return delNode.e;
}
// 从链表中删除第一个元素，并返回
public E removeFirst(){
    return remove(0);
}
// 从链表中删除最后一个元素，并返回
public E removeLast(){
    return remove(size-1);
}
复制代码

向链表中查询及修改元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 改
public void set(int index,E e){
    if(index<0 || index>=size)
        throw new IllegalArgumentException("Index is Illegal");

    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    prev.next.e = e;
}
// 查
public E get(int index){
    if(index<0 || index>=size)
        throw new IllegalArgumentException("Index is Illegal");
    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    return prev.next.e;
}
// 获得链表的第一个元素
public E getFirst(){
    return get(0);
}
// 获得链表的最后一个元素
public E getLast(){
    return get(size-1);
}
复制代码

代码链接

链表的时间复杂度分析

我们现在来看一下链表的增删改查各个操作的时间复杂度：

  • 向链表中添加元素
    与动态数组相反，在动态数组的末尾添加元素的时间复杂度为O(1),在头部添加元素则需要将数组整体向后挪动，需要O(n)的时间复杂度。链表的添加元素操作中，在链表头添加元素的时间复杂度为O(1),在链表尾部添加元素,需要将链表遍历一遍，所以时间复杂度则为O(n)。
  • 向链表中删除元素
    在链表头部删除元素非常简单，时间复杂度为O(1)。删除链表尾部还是需要将链表整体遍历，所以时间复杂度为O(n)。
  • 链表中查询元素
    链表不具备数组的下标索引这种快速查询的机制，所以对于链表来说，查询元素的时间复杂度为O(n)。因为只有将链表进行遍历，才能知道链表中是否有你想要查询的元素，对于链表来说，查询元素这个功能是不利的，事实上，也确实如此。选择了链表这种数据结构主要的操作都是在增删上，而数组这种数据结构则更加适合查询操作，因为数组的索引特性使得查询操作为O(1)的时间复杂度。
  • 链表中修改元素
    对于链表的修改元素这一操作来说，在链表头操作的时间复杂度为O(1),在链表尾修改元素的时间复杂度则是O(n)。

使用链表实现栈与队列

栈与队列是两种特殊的线性数据结构，它们都是基于某种线性数据结构作为底层进行实现的。动态数组作为底层可以实现栈与队列，并且我们使得栈这种数据结构的各个操作均为O(1)的时间复杂度，而队列在使用数组作为底层实现时，出队操作的时间复杂度为O(n),但是循环队列则做出了改进，将队列的各个操作优化至O(1)。我们再回顾一下栈与队列的接口方法：
Stack 

1
2
3
4
5
6
7
8
9
10
11
public interface Stack<E> {
    // 入栈
    void push(E e);
    // 出栈
    E pop();
    // 查看栈顶元素
    E peek();
    int getSize();
    boolean isEmpty();
}
复制代码

Queue 

1
2
3
4
5
6
7
8
9
10
11
public interface Queue<E> {
    // 入队
    void enqueue(E e);
    // 出队
    E dequeue();
    // 查看队首的元素
    E getFront();
    int getSize();
    boolean isEmpty();
}
复制代码

如果将栈与队列的底层变为链表，那么如何进行实现呢？

LinkedListStack

对于链表来说，在链表头操作元素均为O(1)的时间复杂度，而栈是一种仅在栈顶进行push与pop的特殊的数据结构。所以我们的思路非常简单，将链表头作为栈顶就可以使得栈的相关操作为O(1)的时间复杂度了， 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class LinkedListStack<E> implements Stack<E> {

    private LinkedList<E> list;

    public LinkedListStack(){
        list = new LinkedList<>();
    }

    @Override
    public int getSize(){
        return list.getSize();
    }

    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }

    @Override
    public void push(E e){
        list.addFirst(e);
    }

    @Override
    public E pop(){
        return list.removeFirst();
    }

    @Override
    public E peek(){
        return list.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    public static void main(String[] args) {

        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

LinkedListQueue

队列和栈不同，因为FIFO的这种特性，就需要在队列的两头进行操作(从一端添加元素，从另一端删除元素)。对于数组和链表两种数据结构来说，无论是哪一种，在两端进行操作的时间复杂度必是O(1)和O(n)。对于数组来说，我们使用了循环队列这种思想对出队操作进行优化，对于链表也必然有优化的方法，试想一下，在链表头部进行操作的时间复杂度为O(1),如果在链表的尾部也添加一个变量进行维护，那么每次在添加元素时，只需要让尾部指向新添加的元素，并且再次让维护链表尾部的这个变量指向最后一个元素不就可以了吗？假设维护链表尾部的这个变量叫做”tail”,在每次向链表中添加元素时，我们只需要tail.next = newNode;tail = newNode就可以了，这样在链表尾部添加元素就会变为一个时间复杂度为O(1)的操作。

image-20190803092601706

而链表头无论是删除元素还是添加元素都是O(1)，我们可以将链表尾部变为队列尾，将链表头当作队列头。 我们只看入队操作和出队操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 链表为底层的队列：入队
@Override
public void enqueue(E e){
    Node node = new Node(e);
    if(isEmpty()){
        head = node;
        tail = node;
    }else{
        tail.next = node;
        tail = tail.next;
    }
    size++;
}
复制代码
// 链表为底层的队列：出队
@Override
public E dequeue(){
    if(isEmpty())
        throw new IllegalArgumentException("Queue is Empty");
    Node retNode = head;
    if(head==tail){
        head = null;
        tail = null;
    }else{
        head = head.next;
    }
    size--;
    retNode.next = null;
    return retNode.e;
}

总结⭐️

1 链表定义

image-20190803092729208

image-20190803092739868

image-20190803093030340

image-20190803093106999

image-20190803093120357

image-20190803093356580

image-20190803093642404

image-20190803094626616

2 在链表头部添加元素

image-20190803095517695

image-20190803095602692

image-20190803095637469

image-20190803095650562

image-20190803095709760

image-20190803100624006

1
2
3
4
5
6
7
8
9
10
11
 //在链表头部添加元素E e
    public void addFirst(E e) {
        //创建一个新的节点 Node 一个空格存放元素e
        Node node = new Node(e);
        //让这个新的节点指向链表的head
        node.next = head;
        //将head赋值给新创建的head
        head = node;
        //维护size
        size++;
//head=new Node(e,head); size++;

3 在链表中间添加元素

  • 问题分析

    image-20190803101140731

  • 创建一个Node node 存放666 然后找到索引为2之前的那个prev元素 遍历链表找

image-20190803101249413

image-20190803101259790

  • 将Node的下一个元素指向prev的下一个元素

image-20190803101334298

  • 让Prev的next等于node
  • image-20190803101414740

image-20190803101438312

image-20190803101447424

![image-20190803101534083](../../../../../Users/apple/Library/Application Support/typora-user-images/image-20190803101534083.png)

image-20190803102715222

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//在链表index位置添加元素E e
public void add(Integer index, E e) {
        //设置一个Node prev 从Node head开始
        Node prev = head;
        //从头部索引为0的地方开始 直到索引-1的位置遍历 让prev指向下一个
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;
            size++;
        }
   }
 //在链表尾部添加元素E e
public void addLast(){
  add(size,e);
}

 //在链表头部添加元素E e
    public void addFirst(E e) {
        //创建一个新的节点 Node 一个空格存放元素e
        Node node = new Node(e);
        //让这个新的节点指向链表的head
        node.next = head;
        //将head赋值给新创建的head
        head = node;
        //维护size
        size++;
//head=new Node(e,head); size++;

4 使用虚拟头节点

image-20190803104929692

image-20190803115455783

image-20190803115702062

5 获得索引为index的位置的元素

image-20190803120535271

image-20190803120737390

image-20190803120837225

6 在链表中删除元素

image-20190803121115895

image-20190803121212721

image-20190803121228254

image-20190803121253617

image-20190803121307292

1
2
3
4
5
6
7
8
9
10
11
12
13
//从链表中删除index位置的元素 返回删除的元素
   public E remove(int index) {
       //找到待删除的元素之前那个元素的索引
       Node prev = dummyhead;
       for (int i = 0; i < index; i++) {
           //找到待删除的元素之前的那个节点
           prev = prev.next;
       }
       Node retNode = prev.next;
       retNode.next = null;
       size--;
       return retNode.e;
   }

image-20190803122920242

i=0

prev=dummyhead

prev=prev.next—————————》. prev 在索引为0的位置

i=1

prev=0

prev=prev.next————————————>prev在索引为1的weizhi

i=2 不成立退出循环

待删除的元素retNode=prev.next 索引为2的位置

prev.next=retNode.next 删去索引为2 的元素

retNode=null 销毁这个数据

image-20190803124408143

image-20190803124446079

image-20190803155822246

7 链表实现队列

image-20190803161651137

image-20190803161817740

image-20190803162140573

@@分析

Node retnode 为head表示出队的元素

head=head.next 新的head头节点将跳过retnode直接指向head, next⭐️

retNode.next=null 断开 return retNode.e;

image-20190803162804480

image-20190803165031760

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
@Override
public void enqueue(E e){
    if(tail == null){
        tail = new Node(e);
        head = tail;
    }
    else{
        tail.next = new Node(e);
        tail = tail.next;
    }
    size ++;
}

@Override
public E dequeue(){
    if(isEmpty())
        throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

    Node retNode = head;
    head = head.next;
    retNode.next = null;
    if(head == null)
        tail = null;
    size --;
    return retNode.e;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 public class LinkedListQueue<E> implements Queue<E> {

    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    @Override
    public void enqueue(E e){
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }
        else{
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public E dequeue(){
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null)
            tail = null;
        size --;
        return retNode.e;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while(cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }

    public static void main(String[] args){

        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

image-20190803162236427